package algorithm.t202110;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;

/**
 * @author : 李红磊
 * @version :1.0
 * @date : 2021/10/13 10:37
 * @description :
 */
public class t20211013 {

    /*
        977.有序数组的平方
        给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方
        组成的新数组，要求也按 非递减顺序 排序。
     */
    public int[] sortedSquares(int[] nums) {
        if (nums == null) {
            return null;
        }
        if (nums.length == 1) {
            return new int[]{Math.abs(nums[0] * nums[0])};
        }


        int[] arr = new int[nums.length];


        int l = 0, r = nums.length - 1;

        while (l <= r) {

            for (int i = arr.length - 1; i >= 0; i--) {
                if (nums[l] * nums[l] > nums[r] * nums[r]) {
                    arr[i] = nums[l] * nums[l];
                    l++;
                    continue;

                } else {
                    arr[i] = nums[r] * nums[r];
                    r--;
                    continue;
                }
            }

        }


        return arr;

    }


    /*
        189.旋转数组
        给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

    进阶：

    尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
    你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？

     */
    public void rotate(int[] nums, int k) {
        if (nums == null) {
            return;
        } else if (nums.length == 1) {
            return;
        }
        int count = k % nums.length;

        reverse(nums, 0, nums.length - 1);

        reverse(nums, 0, count - 1);
        reverse(nums, count, nums.length - 1);


    }

    public int[] reverse(int[] arr, int l, int r) {
        if (arr == null) {
            return null;
        } else if (arr.length == 1) {
            return arr;
        }


        while (l <= r) {

            int temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
            l++;
            r--;

        }
        return arr;
    }



    /*
        283.移动零
        给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，
        同时保持非零元素的相对顺序

        示例:

        输入: [0,1,0,3,12]
        输出: [1,3,12,0,0]
        说明:

        必须在原数组上操作，不能拷贝额外的数组。
        尽量减少操作次数

     */

    public void moveZeroes(int[] nums) {
        if (nums == null) {
            return;
        } else if (nums.length == 1) {
            return;
        }

        int slow = 0, fast = 1;

        while (fast < nums.length) {

            if (nums[slow] != 0) {
                slow++;
                fast++;
                continue;
            }

            if (nums[fast] == 0) {
                fast++;
                continue;
            }

            int temp = nums[slow];
            nums[slow] = nums[fast];
            nums[fast] = temp;

            slow++;
            fast++;


        }


    }


    /*
        167.两数之和2--输入有序数组

        给定一个已按照 非递减顺序排列  的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。

        函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。

        你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素

     */
    public int[] twoSum(int[] numbers, int target) {

        if (numbers == null || numbers.length == 1) {
            return null;

        }

        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(numbers[0], 1);


        for (int i = 1; i < numbers.length; i++) {
            int num = target - numbers[i];

            if (map.containsKey(num)) {
                return new int[]{map.get(num), i + 1};
            } else {
                map.put(numbers[i], i + 1);
            }


        }
        return null;

    }


    //面试题01.01 判断字符是否唯一
    public boolean isUnique(String astr) {
        if (astr == null || astr.length() == 1) {
            return true;
        }

        boolean flag = true;

        HashSet<String> hashSet = new HashSet<>();
        for (int i = 0; i < astr.length(); i++) {

            if (!hashSet.add(String.valueOf(astr.charAt(i)))) {
                flag = false;
                break;
            }

        }

        return flag;

    }

    //面试题01.02 判断是否互为字符重排
    public boolean CheckPermutation(String s1, String s2) {
        if (s1.length() != s2.length()) {
            return false;
        }

        if (s1.length() == 1 && s2.length() == 1) {
            return s1.equals(s2);
        }

        int[] father = new int[123];
        int[] son = new int[123];

        char[] faChar = s1.toCharArray();
        char[] sonArr = s2.toCharArray();

        for (int i = 0; i < faChar.length; i++) {
            father[faChar[i]]++;

        }
        for (int i = 0; i < sonArr.length; i++) {
            son[sonArr[i]]++;

        }

        return Arrays.equals(father, son);


    }


    //面试题01.03 URL化
    public String replaceSpaces(String S, int length) {
        char[] chars = S.toCharArray();
        StringBuilder builder = new StringBuilder();

        for (int i = 0; i < length; i++) {
            if (chars[i] == ' ') {
                builder.append("%20");
                continue;
            }
            builder.append(chars[i]);

        }


        return builder.toString();
    }

    //面试题01.04 回文排列
    public boolean canPermutePalindrome(String s) {

        HashSet<Object> hashSet = new HashSet<>();
        for (int i = 0; i < s.length(); i++) {

            if (hashSet.contains(s.charAt(i))) {
                hashSet.remove(s.charAt(i));
            } else {
                hashSet.add(s.charAt(i));
            }

        }
        return hashSet.size() <= 1;
    }


    //面试题01.05 一次编辑
    public boolean oneEditAway(String first, String second) {


        if (Math.abs(first.length() - second.length()) >= 2) {
            return false;
        }

        int fLen = first.length();
        int secLen = second.length();

        boolean flag = true;

        //走到这，说明两者长度差小于等于1
        for (int f = 0, s = 0; f < fLen && s < secLen; ) {

            if (first.charAt(f++) == second.charAt(s++)) {

                continue;
            }


            if (!flag) {//只有一次错误的机会，下次再走到这就直接返回false
                return false;
            }

            flag = false;


            //这里的逻辑是针对两个长度相差1 的情况考虑，如pale 和 ale，短的那个需要向前挪一步
            if (fLen != secLen) {
                if (fLen > secLen) {
                    s--;
                } else {
                    f--;
                }

            }

        }
        return true;

    }


    //面试题01.06 字符串压缩
    public String compressString(String S) {
        if (S == null) {
            return null;
        }else if(S.length()==1||S.length()==0){
            return S;
        }

        char sign=S.charAt(0);

        int[] arr = new int[123];
        StringBuilder builder = new StringBuilder();

        for (int i = 0; i < S.length(); i++) {
                if(S.charAt(i)!=sign){
                    builder.append(sign).append(arr[sign]);
                    arr[S.charAt(i)]=0;
                    sign=S.charAt(i);
                    arr[S.charAt(i)]++;
                    continue;
                }
                arr[S.charAt(i)]++;

        }
        builder.append(sign).append(arr[sign]);
        return builder.toString().length()<S.length()?builder.toString():S;


    }


    public static void main(String[] args) {
        t20211013 t20211013 = new t20211013();
        int[] tesArr = {1, 2, 3, 4, 5, 6, 7};

        String str = "Mr John Smith    ";
        System.out.println(t20211013.replaceSpaces(str, 13));


    }


}
